package com.example.leetcode.graph;

import com.example.leetcode.graph.common.GraphUtils;

class Solution743 {
    public int networkDelayTime(int[][] times, int n, int k) {
//        // dijkstra
//        GraphUtils.networkDelayTime(times, n, k);
//        // dijkstra
//        GraphUtils.networkDelayTime3(times, n, k);

        // 堆优化后的 dijkstra
       return  GraphUtils.networkDelayTime4(times, n, k);
//        // 堆优化后的 dijkstra
//        GraphUtils.networkDelayTime6(times, n, k);
//
//        // floyd
//        GraphUtils.networkDelayTime1(times, n, k);
//        // floyd
//        GraphUtils.networkDelayTime9(times, n, k);
//
//        // 也可以使用动态规划
//
//        // 也可以使用 bellman ford 算法基础版
//
//        // Bellman Ford 优化版
//        GraphUtils.networkDelayTime2(times, n, k);
//        // Bellman Ford 优化版
//        GraphUtils.networkDelayTime5(times, n, k);
//
//        // SPFA
//        GraphUtils.networkDelayTime7(times, n, k);
//        // SPFA
//        GraphUtils.networkDelayTime8(times, n, k);

//        return 0;
    }
}

public class leetcode743 {
    public static void main(String[] args) {
        Solution743 solution743 = new Solution743();
        int[][] times = {
                {2, 1, 1},
                {2, 3, 1},
                {3, 4, 1}
        };
        int[][] times1 = {
                {1, 2, 1}
        };
        int[][] times2 = {
                {1, 2, 1}
        };
        int[][] times3 = {
                {1, 2, 1},
                {2, 3, 7},
                {1, 3, 4},
                {2, 1, 2}
        };
        System.out.println(solution743.networkDelayTime(times, 4, 2)); // 2
        System.out.println(solution743.networkDelayTime(times1, 2, 1)); // 1
        System.out.println(solution743.networkDelayTime(times2, 2, 2)); // -1
        System.out.println(solution743.networkDelayTime(times3, 4, 1)); // -1
    }
}
